Multiprocessor architectures provide powerful computer systems which, by subdivision of tasks between processors, can handle complex problems and manipulate large data bases quickly and reliably. With most architectures, however, the overhead of managing the resources of the system can become so complex and time consuming that it can severely limit system performance. The processors must intercommunicate among themselves, prioritize different messages, and execute various tasks in the most efficient manner. Depending upon the architecture, this has required the development of very complicated software overhead for system resource management.
Such factors, along with the difficulty of writing software and complex procedures for system expansion, have in the past limited the application of multiprocessor systems. Most multiprocessors utilize single or double intercommunication busses with priority being determined in accordance with an assigned hierarchy or on the basis of time. Control functions are exercised by specific processors, or by bus controllers, or by a variety of other means.
Recognizing the extent of these and other problems, a new multiprocessor system has been introduced and is now in widespread use, based upon the concepts shown and described in U. S. Pat. No. 4,412,285 to Philip M. Neches et al and U. S. Pat. Nos. 4,445,171 and 4,543,630 to Philip M. Neches. A significantly different approach is used in these systems, which communicate between processors by an active logic network having a tree configuration and means for prioritizing messages based upon data content. The tree network also broadcasts messages having priority to all processors. Local determinations are made, at the processors, as to messages to be responded to or processed by those processors. Data, status, control and response messages are organized in a coherent priority scheme that, together with the system architecture, greatly reduces the complexity of the overhead functions and enables ready expansion of the system to a very large (e.g. 1,024 processor) configuration. This system has proven to be of unique significance, for example, in deriving complex relational queries from vast data bases which may have hundreds of state of the art processors handling up to 10.sup.12 bytes (terabytes) of stored data. In the relational data base situation the contents must be constantly updated, extracted, processed and modified as entries are made and complex relational queries are answered
The referenced patents describe a variety of approaches utilized in communications between processors. All of the processors can be addressed by a broadcast mode, or at the other extreme specific processors can intercommunicate by identification of a particular recipient. Processors can also be designated in accordance with data responsibility ("hashed mode") or as a participant in a pre-identified group. Such groups are established during an initialization process and thereafter are not changed except by returning to initialization. Every message is addressed to all members of the group concurrently, only those processors which are members of the group acknowledge the message and process data contributing to the completion of the given task.
Besides interprocessor communication, a practical system must provide means for external communication Good examples of these needs can be found in the "Backend Processor" configuration described in the referenced patents, in which the multiprocessor system is utilized to update the data base and answer relational data base queries from one or more mainframe computers. Communication with the mainframe is effected by interface processors which usually, but not necessarily, accept assignments from the mainframe system and parse the task into substeps, messages for which are then transmitted into the network.
As the various subtasks are being carried out, it is necessary to be able to monitor progress of the responsible processors toward completion. It is also necessary to be able conveniently to restore the data base if an erroneous or unacceptable condition arises as a transaction is carried out. For example, transfers of funds between accounts may be undertaken before it is subsequently determined that the transaction is invalid because some funds are inadequate. In these circumstances, the already completed steps must be reversed in order to restore data to its prior status. This means that the processors then involved in other subtasks of the aborting transaction should not only restore their data but terminate their efforts, and accept no new subtask assignments for the aborting transaction.
Also, the system operates with Begin Transaction and End Transaction phases needed to achieve coordination and eliminate ambiguity. In the Begin Transaction phase the originating processor, by one or more messages on the network, involves all processors that are members of some process class, preparing them to receive and process the specific "steps" or subtasks of the transaction Similarly, all members of the process class are again involved in the End Transaction phase.
In the system described in the original Neches et al patents, the process class is necessarily large, because such process classes are established during system initialization and are intended to encompass many different types and categories of transactions. Because in many circumstances only a small subgroup of a process class may be involved in a given transaction, there can be an undesired level of overhead activity and processor time committed to overhead functions. The members of a process class are identified and addressed by a Destination Selection Word (DSW), which when used with a hashing algorithm enables any processor containing specifically sought data to recognize the applicability of a query and to respond. Because given tasks often involve only small subgroups within a given DSW, system efficiency can substantially decline when many simple transactions are to be undertaken.
The group subdivisions or "partitions" can change frequently in some workloads. Also, obtaining efficient use of system resources may involve many different group subdivisions, entailing overlapping combinations of processors that are active at the same time, as many different transactions are carried out concurrently by the system. Consequently, there is a need for a capability for partitioning multiple concurrent subgroupings of processors in a system which can also eliminate conflicting states and which can dynamically change these groupings as needed.
The problem of changing the operative relationship of parallel processors has been confronted in a number of different ways in conjunction with specific systems. In U. S. Pat. No. 4,344,134 to George H. Barnes, dated Aug. 10, 1982 and entitled "Partitionable Parallel Processor", for example, a number of parallel processors are each coupled to a control tree having tiers of control nodes. The control nodes may function as roots or non-roots under control signals. When the processors arrive at a Ready State, for beginning a parallel processing instruction, they issue a so-called "I Got Here" signal. The control signals applied to the nodes cause them to function when appropriate as a root node, returning a "GO" signal to initiate the instruction, or as a non-root node, feeding the signal on to the next lower level node. Using the nodes of the control tree in this fashion, the processors may be partitioned into subsystems of parallel processors.
In U. S. Pat. No. 4,347,498 of Robert P. Lee et al, entitled "Method And Means For Demand Accessing And Broadcast Transmission Among Ports In A Distributed Star Network" the Star Network has a number of interconnected nodes, each directly connected to one or more ports. The ports in turn may be connected to different computers or peripheral devices. This arrangement is used for packet switching on a first-come first-served basis from any of the ports so as to broadcast to all of the ports.
U. S. Pat. No. 4,099,233, entitled "Electronic Data-Processing System With Data Transfer Between Independently Operating Miniprocessors", issued July 4, 1978 to Giuseppe Barbagelata et al, employs a control unit to control exchanges between transmitting and receiving processors in a data transfer operation. The control unit establishes "exchange miniprograms", and includes an instruction register for retaining the identities of the transmitting and receiving miniprocessors.